package main

func closestCost(baseCosts []int, toppingCosts []int, target int) int {
	var ans int = baseCosts[0]
	for _, c := range baseCosts {
		ans = min(ans, c)
	} // 更新默认值  最小值
	var dfs func(p int, curCost int)
	dfs = func(p int, curCost int) {
		if abs(ans-target) < curCost-target {
			return // 剪枝
		} else if abs(ans-target) >= abs(curCost-target) {
			// 更新
			if abs(ans-target) > abs(curCost-target) {
				ans = curCost
			} else {
				ans = min(ans, curCost)
			}
		}
		if p == len(toppingCosts) {
			return // 边界
		}

		// 搜索
		dfs(p+1, curCost+toppingCosts[p]*2) // 每种配料最多两份
		dfs(p+1, curCost+toppingCosts[p])
		dfs(p+1, curCost)
	}
	for _, c := range baseCosts {
		dfs(0, c) // 更换每种主料
	}
	return ans
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}
